package sortQuestion

import (
	"container/heap"
)

/**
题目
已知一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离一定不超过k，并且k相当于数组长度是比较小的
请选择一个合适的排序方法，进行排序
*/

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func KSort(data []int, k int) []int {
	cnt := len(data)
	if cnt < 2 {
		return data
	}

	kHeap := IntHeap{}
	kHeap = append(kHeap, data[:min(cnt, k)]...)
	heap.Init(&kHeap)

	for i := k; i < cnt; i++ {
		data[i-k] = heap.Pop(&kHeap).(int)
		heap.Push(&kHeap, data[i])
	}

	for i := k; i > 0; i-- {
		data[cnt-i] = heap.Pop(&kHeap).(int)
	}

	return data
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}
